import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.ByteArrayOutputStream;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Writer;
import java.util.*;
import java.util.Map.Entry;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.zip.Deflater;

/**
 Team: Name: Seungbeom Ma / Lok Kei Leong /Harini Padmanaban
 Reference: Wiki , discussion with classmates , lecture , lecture note, textbook
 Java api and example website.
 */


public class IndexPrinter{
        
    static int totTokens,docCount=0;
    static double[] docScore;
    static int[] docFlag;
    static int cache=1,collTermPos=0;
    static String[] termArr = new String[20];
    
    	static ArrayList<ArrayList<Integer>> docNumber1 = new ArrayList<ArrayList<Integer>>();
        static ArrayList<String> tokenList = new ArrayList<String>();
        static Hashtable<String,Integer> hashTermSearch = new Hashtable<String,Integer>();
        static Hashtable<String,ArrayList<Integer>> termDocList = new Hashtable<String,ArrayList<Integer>>();
        static Hashtable<String,ArrayList<Integer>> termPosList = new Hashtable<String,ArrayList<Integer>>();
        static Hashtable<String,ArrayList<Integer>> termIndexList = new Hashtable<String,ArrayList<Integer>>();
        static Hashtable<Integer,Double> hashDocProxScore = new Hashtable<Integer,Double>();
        static int tc = 0;
        
        public static void main(String[] args) throws IOException, InterruptedException {
                
                
                
                for(int p=0;p<20;p++)
                {
                	docNumber1.add(p, new ArrayList<Integer>());  
                	
                }
                /**
                 *  The first file Steam . It is reading the PointIndex
                 *   FileInputStream fstream1 = new FileInputStream(args[0]);
                 *  
                 */
                /**
                 * HW 4 PART
                 * */
                String query1 = " ";
                String query_al = "";
                
                if(args.length == 3)
                {
                	   query1 = new String(args[1]);
                       query_al = new String(args[2]);
                }
                else{
                	query_al = new String(args[1]);
                }
                ArrayList<String> AllDocInOneLine = new ArrayList<String>();
                
                /**
                 * HW 4 PART END
                 * */
                /**
                 *PointIndex: catching the String value from the stringTokenizer
                 * 
                 * */
                
                String strLine = null;              
                String keyword = null;     
                
                  
                int documentCounter = 1;
                int detectDoc = 0;
                /**
                 * HW2
                 * */
               
                int tracker = 0;      
                int HowManyTimeKeywordAppearInThisDoc = 0; 
                int savecounter = 0;        
                int howManyDocAppear = 0 ;
                int totalnumberofdocs = 1;
                Hashtable<Integer, Integer> HowmanytimeeachQueryApear =  new Hashtable<Integer,Integer>();
                /** AllDocContainer is containing all string of each doc
                * ex) AllDocContainer(1, "bob is good and bad")
                * ex) AllDocContainer(2, "this clas is really good and cool"
                */
                HashMap<Integer, String>  AllDocContainer = new HashMap<Integer, String>();             

                Hashtable<Integer , String> htDocCounter = new Hashtable<Integer , String>();
                /** this is the hashtable to store the document numbers which contain keyword*/
                Hashtable<Integer, Integer> DocsThatKeywordAppear = new Hashtable<Integer, Integer>();
                /** this is the hashtable to store how many time keyword is appear on each doc */
                Hashtable<Integer, Integer> HowManyTimeKeyWordAppearInEachDoc = new Hashtable<Integer, Integer>();
                /**this is arraylast to store the keyword from the text file.*/
                      
                        keyword = query1; 
                        StringBuffer testString = new StringBuffer();
                        
                        FileInputStream fstream = new FileInputStream("/Users/seungbeomma/Documents/workspace/CSE267HW2/src/my_test_file.txt/");
                      
                        DataInputStream in = new DataInputStream(fstream);
                        BufferedReader br = new BufferedReader(new InputStreamReader(in));
                        while ((strLine = br.readLine()) != null)   { 
                                StringTokenizer stringTokenizer = new StringTokenizer(strLine);
                                int EndOftheParagraph = 0;
                                /**
                                 * If paragrah is more than one like then we have to appead line + line 
                                 * therefore we need to sperate by empty space " " 
                                 * */
                                testString = testString.append(strLine + " "); 
                                                                                                
                        
                                Scanner sc = new Scanner (strLine);
                                while(sc.hasNext())
                                {
                                        sc.next();
                                        EndOftheParagraph++;
                                }                                     
                                if(EndOftheParagraph == 0)
                                {/** It is the end of paragraph, so we are reading new file*/
                                        
                                        savecounter++; /**increase counter for next document  */ 
                                        HowManyTimeKeywordAppearInThisDoc = 0;/** since we are moving to new doc*/                                 
                                }
                                if(stringTokenizer.countTokens() == 0)
                                { 		/**if token is done it's end of doc
                                         * testString = stringBuffer 
                                         * need to convert stringBuffer to String 
                                         * `SortAllDoc <documentCounter = doc_id  , sec = praragraph for each document
                                         * */
                                        String sec = testString.toString();
                                        AllDocContainer.put(documentCounter, sec);
                                        
                                        /**
                                         * One document is done, so We need to clean StringBuffer
                                         * In order to prepare for next document, we need to delete
                                         * content of StringBuffer testString.. 
                                         * */
                                        testString.delete(0,testString.length() );
                                        documentCounter++; 
                                        totalnumberofdocs++;
                                        
                                        /** if it is moving to new document, we need to initialize 
                                        * HowManyTimeKeywordAppearInThisDoc again for counting keyword from
                                        *  another doc      */                                                                                                                             
                                }
                                while(stringTokenizer.hasMoreElements()){ 
                                        String lowercaseWordFromParagraph = stringTokenizer.nextToken().toLowerCase();
                                        if(lowercaseWordFromParagraph.equals(keyword)){ 
                                                
                                                HowManyTimeKeywordAppearInThisDoc++; /** increase number of keyword in this document*/
                                                /** this hashtabl is recording how many time keyword is appearing in each document*/
                                                HowManyTimeKeyWordAppearInEachDoc.put(savecounter, HowManyTimeKeywordAppearInThisDoc);                                                                                                              
                                                if(!htDocCounter.containsKey(documentCounter))                                                     
                                                {/** If new document contains keyword  
                                                         *
                                                         * htDocCounter => keyword
                                                         * DocsThatKeywordAppear -> document id that keyword in the htDocCounter 
                                                         * */
                                                        htDocCounter.put(documentCounter, lowercaseWordFromParagraph); /** we put keyword in the hashtable*/
                                                        DocsThatKeywordAppear.put(detectDoc, documentCounter); /** we also put document number in the hashtable */
                                                        
                                                        detectDoc++; /** for next keyword, we increare key in hashtable*/
                                                        
                                                        howManyDocAppear++;           

                                                }          

                                        }
                                        
                                }       
                      
/** howManyDocAppear:How many doc has "keyword" 
 * keyWordIndex: total number of times appear in docs
 * list1: which doc contains "keyword"
 * list2: how many time appear the "keyword" in the List1
 * 
 * 
 * */
        
                                String lastStrLine =  " ";
                                lastStrLine = strLine.toString();
                                AllDocContainer.put(documentCounter, lastStrLine);


/**
 * tracker: denominator of idf
 */
tracker =  tracker + howManyDocAppear;


/** To make display form, we copy two hashtables values to arraylist.*/
        ArrayList<Integer> list1 
                = new ArrayList<Integer>(DocsThatKeywordAppear.values());
        ArrayList<Integer> list2 
        = new ArrayList<Integer>(HowManyTimeKeyWordAppearInEachDoc.values());
        ReverceList(list1);
        ReverceList(list2);
/** HowmanytimeeachQueryApear
 * Key = docuement number
 * key2 = homany time query appear in the each docs
 */
for(int printerIndex = 0 ; printerIndex <list2.size() ; printerIndex++)
{

        HowmanytimeeachQueryApear.put(list1.get(printerIndex),list2.get(printerIndex));
        
}
                        /** one looping is done , so we need to re-set all variable
                        * and hashtable for another keyword*/
                        
                        howManyDocAppear = 0;
                        savecounter = 0;
                        detectDoc =0;
                    
                        htDocCounter.clear();
                        DocsThatKeywordAppear.clear();
                        HowManyTimeKeyWordAppearInEachDoc.clear();
                                    
                } 

                        
                        Iterator<Entry<Integer, Integer>>  it;
                        Map.Entry entry;

            if (query_al.equals("cosine")){
  
                                int numofdoc = AllDocContainer.size();
                                int len=0,next=0;
                                calculate(query1,numofdoc, AllDocContainer);
                                                               
                                while(termArr[next] != null)
                                {
                                        len++;
                                        next++;
                                }
                                
                                for (int i=0;i<len;i++)
                                {       
                                        updateDocList(termArr[i],AllDocContainer,numofdoc);
                                }

                if (CountingWord(query1) == 1){
                        
                        double tf = 0.0;
                    ArrayList<Integer> docidList1 = new ArrayList<Integer>();
                    ArrayList<Double> rankList1 = new ArrayList<Double>();
                    ArrayList<Double> sortList1 = new  ArrayList<Double>();
                        double idf = 
                                        Math.log((double)((double)totalnumberofdocs/(double)tracker))/Math.log(2.0);
            

                    it = HowmanytimeeachQueryApear.entrySet().iterator();
                    while (it.hasNext()) {
                        entry = it.next();
                                
                  
                                int temp = 0;
                                while(true){    
                                 temp =  (Integer) entry.getValue();                                         
                                tf = (Math.log(temp)/Math.log(2) )+ 1;
                           
                                break;
                            }
                            float tfidf = (float)idf * (float)tf;
                            
                                docidList1.add((Integer)entry.getKey());
                                rankList1.add((double) tfidf);
                   
                                sortList1.add((double) tfidf);
                           
                    }
                    Collections.sort(sortList1);
                    Collections.reverse(sortList1);
                    int luisatracker = 0;
                    for(int matchLuisa = 0 ; matchLuisa < sortList1.size() ; matchLuisa++)
                    {
                   
                         for(int bob = 0 ; bob < sortList1.size() ; bob++ ){

                                 if(sortList1.get(matchLuisa).equals(rankList1.get(bob)))
                                 {
                                        luisatracker++;
                                      
                                         System.out.println("( " + docidList1.get(bob) + " , " + sortList1.get(matchLuisa) +" )" );
                                         
                                 }
                                 
                         }
                          if(luisatracker == sortList1.size())
                          {
                                  break;
                                  
                          }
                    } 
                }
                    else 
                    {
                        /**
                         * wordscontainer: storing each word in the
                         * query. 
                         * if query is "Bob ma" 
                         * wordscontainer[0] = Bob
                         * wordscontainer[1] = ma
                         */
                  
                    	
                         String[] wordscontainer = returnWord(query1);
                       
                         /**containsDocnumberthatcontainAllQuery will contain doc number
                         * which contains all words in query.
                         * tfidfarray array contains tfidf value for each docs*/
                         float [] tfidfarray = new float[AllDocContainer.size()+1];
                         int AllDocIndex = 1;
                         int counter = 0;
                         int whatsize = 0;
                         ArrayList<String> aListNumbers = new ArrayList<String>();
                         for(int i = 1 ; i < AllDocContainer.size()+1 ; i++ )
                         {
                                 for(int j = 0 ; j < wordscontainer.length ; j++)
                                 {

                                         String[] numbers = AllDocContainer.get(i).split(" ");

                                         for(int q=0; q< numbers.length; q++)
                                         {
                                                 
                                                 aListNumbers.add(numbers[q]);
                                         }
                                         
                                         if(aListNumbers.contains(wordscontainer[j]))
                                         {
                                                 counter++;
                                                 
                                         }
                                         
                                 }
                                 aListNumbers.clear();
                                 if(counter == wordscontainer.length )
                                 {
                                         whatsize++;
                                         
                                 }
                                 counter=0;
                                 
                         }
                        ArrayList<Integer> docidList = new ArrayList<Integer>();
                        ArrayList<Double> rankList = new ArrayList<Double>();
                        ArrayList<Double> Luisa = new  ArrayList<Double>();
                         
                         while(AllDocIndex <= AllDocContainer.size())
                         {
                                 
                             tfidfarray[AllDocIndex] = 
                                         getTFIDF(wordscontainer,AllDocContainer,AllDocIndex , AllDocContainer.size(), whatsize);
                             AllDocIndex++;
                         }
                            
                             for(int index3 = 1 ; index3 <= AllDocContainer.size(); index3++){
                                  /** if every anyterm is not appear in the doc then 
                                   * getTFIDF will return -9999999
                                   * so skip print part
                                   */
                                  if(-9999999 != tfidfarray[index3]){
                                       
                                                docidList.add(index3);
                                                rankList.add((double) tfidfarray[index3]);
                               
                                                Luisa.add((double) tfidfarray[index3]);
                                                
                                  }
                             }
                             Collections.sort(Luisa);
                             Collections.reverse(Luisa);
                             
                             ArrayList<Integer> preventdup = new ArrayList<Integer>();
                             for(int matchLuisa = 0 ; matchLuisa < Luisa.size() ; matchLuisa++)
                             {
                            
                                 for(int bob = 0 ; bob < Luisa.size() ; bob++ ){

                                         if((Luisa.get(matchLuisa).equals(rankList.get(bob))&&(!(preventdup.contains(docidList.get(bob))))))
                                         {
                                                 
                                                 preventdup.add(docidList.get(bob));
                                                 System.out.println("( " + docidList.get(bob) + " , " + Luisa.get(matchLuisa) +" )" );
                                                 
                                         }
                                 }
                             }                                            
                        }                               

                        }
                        else if (query_al.equals("boolean")) {
                                
                                int numberofDoc = AllDocContainer.size();
                                calculate(query1,numberofDoc, AllDocContainer);
                                ArrayList<Integer> docidList1 = new ArrayList<Integer>();
                                ArrayList<Double> rankList1 = new ArrayList<Double>();
                                ArrayList<Double> Luisa1 = new  ArrayList<Double>();
                                 
                                
                                for(int index=0; index< numberofDoc;index++)
                                {
                                        if(docFlag[index]==1)
                                        {
                                             
                                                docidList1.add((index+1));
                                                rankList1.add(docScore[index]);
                                                Luisa1.add(docScore[index]);
                                        }
                                }
                                
                               Collections.sort(Luisa1);
                                Collections.reverse(Luisa1);
                                ArrayList<Integer> preventdup1 = new ArrayList<Integer>();
                                for(int matchLuisa1 = 0 ; matchLuisa1 < Luisa1.size() ; matchLuisa1++)
                                {
                               
                                    for(int bob1 = 0 ; bob1 < Luisa1.size() ; bob1++ ){

                                            if((Luisa1.get(matchLuisa1).equals(rankList1.get(bob1))&&
                                            			(!(preventdup1.contains(docidList1.get(bob1))))))
                                            {
                                                   
                                            	preventdup1.add(docidList1.get(bob1));
                                                    System.out.println("( " + docidList1.get(bob1) + " , " + Luisa1.get(matchLuisa1) +" )" );
                                                    
                                            }
                                    }
                                } 
                                
                                
                        }
            /**
             * part 3 from bob
             * */
                        else if (query_al.equals("bm25")) {
                        /**
                         *  beginning for bm25
                         */
                        
                        	 String[] bm25QueryList = returnWord(query1); 
                        	 ArrayList<String> allDocInArrayList = HashvalueToArrayList(AllDocContainer);
                        	 ArrayList<Integer> lengthOfAllDoc =  DetermineLenth(allDocInArrayList);
                        	 Hashtable<String, Integer> howmanytimeapper = new Hashtable<String, Integer>();
                        	 Hashtable<String, Double> htBM25IDF = new Hashtable<String, Double>();
                        	 /**
                        	  * for tf part String == each term  , ArrayList<Double> actual TF value for each doc
                        	  */
                        	 Hashtable<String, ArrayList<Double>> tfForAlldoc = new Hashtable<String, ArrayList<Double>>();
                        	 
                        	 double avgLength = avg(lengthOfAllDoc); 
                        	 int totalLength = totalLength(lengthOfAllDoc);
                        	 
                        	 /**
                        	  *  it will store each term's BM25 scores;
                        	  */
                        	 Hashtable<String, ArrayList<Double>> BM25TFIDF = new Hashtable<String, ArrayList<Double>>();
                        	 ArrayList<Double> actualTFvalueforEachDoc = new ArrayList<Double>();
                        	 double finalBM25 = 0.0;
                        	 /**
                        	  *  get the IDF value Key: term in query Value: Double IDF value for each query 
                        	  */
                        	 howmanytimeapper = howManyTimeAppear(allDocInArrayList,bm25QueryList); 
                        	 
                        	 htBM25IDF = BM25IDF(howmanytimeapper ,allDocInArrayList.size() , bm25QueryList);  
                        	
                        	 for(int outer = 0 ; outer < bm25QueryList.length ; outer++)
                        	 {
                        		/**
                        		 * call BM25TF to get TF value for each doc and query
                        		 * Key = word in query , value = ArrayList<Double> contains double values for each documents
                        		 */
                        			 tfForAlldoc.put(bm25QueryList[outer], BM25TF(avgLength,allDocInArrayList ,bm25QueryList[outer], lengthOfAllDoc ));
                        	 }
                        	
                        	 /**
                        	  * time to get bm25 value
                        	  * ArrayList to get the TM value from the  tfForAlldoc 
                        	  */
                        	 double finalIDF = 0.0;
                        	 double finalTM = 0.0;
                        	 double finalBM = 0.0;
                        	 
                        	 ArrayList<Double> finalTMlist = new ArrayList<Double>();
                        	
                        	 /**
                        	  * looping until we finish to read word in the query
                        	  * make sure this is ref value we can not use.clear
                        	  * finalIDF first holding IDF value 
                        	  * finalTMlist holding TF value
                        	  * for loop grap idf and tf . it is time to add all of team for final result
                        	  */
                        	 for(int finalindex = 0; finalindex < bm25QueryList.length ; finalindex++)
                        	 { 
                        		 actualTFvalueforEachDoc =  new ArrayList<Double>();
                        		 finalTMlist  = new ArrayList<Double>();                         
                        		 finalIDF = 0.0;                                          		 
                        		 
                        		 finalIDF = htBM25IDF.get(bm25QueryList[finalindex]);
                        		 
                        		 finalTMlist = tfForAlldoc.get(bm25QueryList[finalindex]);
                        		 
                        		 for(int innerfinal = 0 ; innerfinal < finalTMlist.size() ; innerfinal++ ){
                        			 finalTM =finalTMlist.get(innerfinal);
                        			 finalBM =  finalIDF * finalTM;
                        			 /**
                        			  * IDF* TM to get final value 
                        			  * then put result in to actualTFvalueforEachDoc arraylist
                        			  */
                        			  
                        			 actualTFvalueforEachDoc.add(finalBM); 
                        			 
                        			 finalTM = 0.0;
                        			 finalBM = 0.0;                        			 
                        		 }
                        		 /**
                        		  *  for preparing the final value we put into hashtable <String, ArrayList<Double>>
                        		  *  Key: word in query
                        		  *  Value: ArrayList which contains all BM25 values for each term.
                        		  *  Like {bob = {1,0,1.2131 ,232} hi = {0,0,0,1}}
                        		  */
                        		
                        		 BM25TFIDF.put(bm25QueryList[finalindex], actualTFvalueforEachDoc);         		 
                        	 }
                        	
                        	 ArrayList<Double> realFinalResult = new ArrayList<Double>();
                        	 ArrayList<Double> trackingResult = new ArrayList<Double>();
                        	
                        	 double displayresult = 0.0;
                        	 
                        	 for(int finalindex = 0 ; finalindex < allDocInArrayList.size() ; finalindex++)
                        	 {
                        		 for(int finalinner = 0 ; finalinner < bm25QueryList.length ; finalinner++ )
                        		 {
                        			 /**adding all query values for each doc
									*one by one like get first doc of "bob" value then first doc of "hi"
                        			*then add each other
                        			*/
                        			 displayresult += (BM25TFIDF.get(bm25QueryList[finalinner])).get(finalindex);
                        			 
                        			
                        		 }
                        		 /** 
                        		  * then store into display array result for final display
                        		  */
                        		 realFinalResult.add(displayresult);
                        		 displayresult = 0.0;
                        	 }
                        	
                        	 for(int copy = 0 ; copy < realFinalResult.size() ;copy++)
                        	 {
                        		 trackingResult.add(realFinalResult.get(copy));
                        	 }
                        	
                        	 Collections.sort(realFinalResult);  
                        	 Collections.reverse(realFinalResult); 
                        	 /**
                        	  * Finaldisplay part
                        	  * */
                        	 
                        	 for(int ir = 0 ; ir < realFinalResult.size() ; ir++)
                        	 {
                        		 if(realFinalResult.get(ir) > 0.0)
                        		 {
                        			 
                        			 for(int irr = 0 ; irr < trackingResult.size() ; irr++)
                        			 {
                        				if(trackingResult.get(irr) ==  realFinalResult.get(ir))
                        				{
                        					System.out.println("(" + (irr +1) + "," + realFinalResult.get(ir) + ")");
                        				} 
                        				 
                        			 }
                        			
                        		 }
                        		 
                        		 
                        	 }
                        	 
                        }
                        else if (query_al.equals("proximity"))
                        {
                        	String[] proArray=returnWord(query1);
                        	int noOfDoc = AllDocContainer.size();
                        	
                        	for(int index=1;index<=noOfDoc;index++)
                        	{	
                        		findTermIndex(proArray,AllDocContainer,index);
                        	}	
                        	
                        }
                        else if(query_al.equals("delta"))
                        {
                        	
                        	logrithmicMerge(AllDocContainer);
                        	/**
                        	 * AlldocInDocList: put all term in docs at one arraylist
                        	 * KeyList will contain all unique term in the doc
                        	 * */
                        	ArrayList<String> AlldocInDocList = new ArrayList<String>();
                        	ArrayList<String> KeyList = new ArrayList<String>();
                        	Hashtable<String, ArrayList<Integer>> DeltaBefore = new Hashtable<String, ArrayList<Integer>>();
                        	Hashtable<String, ArrayList<Integer>> Delta = new Hashtable<String, ArrayList<Integer>>();
                        	ArrayList<Integer> position = new ArrayList<Integer>();                      	
                        	AlldocInDocList = AlldocInOne(AllDocContainer);
                        	KeyList = getKeys(AlldocInDocList);
                        	Collections.sort(KeyList);
                        	
                        	for(int first = 0 ; first < KeyList.size() ; first++)
                        	{
                        		for(int second = 0 ; second < AlldocInDocList.size() ; second++)
                        		{
                        			if(KeyList.get(first).equals(AlldocInDocList.get(second))){
                        				 
                        				position.add(second + 1);
                        				
                        			}
                        		}
                        		DeltaBefore.put(KeyList.get(first), position);
                        		 position = new ArrayList<Integer>();
                        	}
                        	position = new ArrayList<Integer>();
                        	
                        	for(int out = 0 ; out < DeltaBefore.size() ; out++)
                        	{
                        		position = FindGap(DeltaBefore.get(KeyList.get(out)));
                        		Delta.put(KeyList.get(out), position);
                        		 position = new ArrayList<Integer>();
                        	}
                        	
                        	Hashtable<String, ArrayList<String>> DeltaString = new Hashtable<String, ArrayList<String>>();
                        	Hashtable<String, ArrayList<String>> GammaEncode = new Hashtable<String, ArrayList<String>>();
                        	ArrayList<String> reAls = new ArrayList<String>();
                        	for(int i = 0 ; i < KeyList.size(); i++){
                        		reAls = DecToBinary(Delta.get(KeyList.get(i)));
                        		DeltaString.put(KeyList.get(i), reAls);
                        		reAls = new ArrayList<String>();
                        	}
                        	reAls = new ArrayList<String>();

                        	for(int ii = 0; ii < KeyList.size(); ii++)
                        	{

                        		reAls =gammaEncoding(DeltaString.get(KeyList.get(ii)));
                        		
                        		GammaEncode.put(KeyList.get(ii), reAls);
                        		reAls = new ArrayList<String>();
                        	}
                        	System.out.println("");
                        	writeGammaFileAndPlanFile(KeyList , DeltaBefore , GammaEncode , args[0]);
                        	System.out.println("GammaEncode " + GammaEncode);
                        	String binary = "";
                        	for(int i = 0 ;  i< KeyList.size() ; i++){
                        		
                        		
                        			binary += ArrayListToString(GammaEncode.get(KeyList.get(i)));
                        			
                        	}
                        	byte[] dataByte =binary.getBytes();
                        	Deflater def = new Deflater();
                        	def.setLevel(Deflater.BEST_COMPRESSION);
                        	def.setInput(dataByte);
                        	def.finish();
                        	 ByteArrayOutputStream byteArray = new ByteArrayOutputStream(dataByte.length);
                        	
                        	   byte[] buf = new byte[1024];
                        	    while (!def.finished()) {
                        	      int compByte = def.deflate(buf);
                        	      byteArray.write(buf, 0, compByte);
                        	    }
                        	    byte[] comData = byteArray.toByteArray();
                        	    
                        	//    FileWriter fs = new FileWriter("testfor compare.txt");
                        	    String filecomp = "";
                            	for ( int i = 0; i < args[0].length(); i++){
                        	    	if (args[0].charAt(i) == '.'){
                        	    		filecomp = args[0].substring(0, i );
                        	    	}
                        	    }
                            	
                            	String filecom = filecomp + "_compress";
                        	    
                        	    FileOutputStream out = new FileOutputStream( filecom +".txt");
                        	    out.write(comData);
                        	    //Close the output stream
                        	    out.close();
                        	
                        }
                        else if(query_al.equals("DFR"))
                        {
                        	
                        	/**
                        	 * 1: Create P1 value
                        	 * P1 represents the probability that a reandom document d contain exactly ftd occurences of t
                        	 * 2: Create p2 value
                        	 *
                        	 *
                        	 * N: number of doc
                        	 * Lt: number of term in collection
                        	 * #of term in each document
                        	 * */
                        	ArrayList<String> AlldocInDocList = new ArrayList<String>();
                        	AlldocInDocList = AlldocInOne(AllDocContainer);
                        	Hashtable<String, ArrayList<Integer>> ftd = new Hashtable<String, ArrayList<Integer>>();
                        	Hashtable<String, ArrayList<Integer>> new_ftd = new Hashtable<String, ArrayList<Integer>>();
                        	Hashtable<String, ArrayList<Double>> result = new Hashtable<String, ArrayList<Double>>();
                        	
                        	int n = AllDocContainer.size();
                        	
                        	Hashtable <String, Integer> lt = new Hashtable<String, Integer>();
                        	lt = howmanytimeappearInDoc(AllDocContainer , args[1]);
                        	ftd = getftd(AllDocContainer , args[1]);
                        
                        	int numberofdoc = AllDocContainer.size();
                        	 int trackers= 0 ;
                              	ArrayList<String> al = new ArrayList<String>();
                              	ArrayList<Integer> ld = new ArrayList<Integer>();
                              for(int o = 1 ;  o < AllDocContainer.size()+1 ; o++){
                            	 int dlenght = 0;
                              		for(String t : AllDocContainer.get(o).split(" "))
                              		{
                              			dlenght++;
                              			trackers++;
                              		}
                              		ld.add(dlenght);
                              }
                              	
                              	
                              	double lavg = trackers/numberofdoc;
                             
                        	
                        	
                        	result = getPone(n,lt,ftd,args[1] ,lavg,ld );
                        	
                        	ArrayList<String> term = getTerms(args[1]);
                        	ArrayList<Double> ResultSets = new ArrayList<Double>();
                        	ArrayList<Double> ReturnResultSets = new ArrayList<Double>();
                        	for(int ii = 0 ; ii < result.get(term.get(0)).size(); ii++){
                        		ReturnResultSets.add(0.0);
                        	}

                        	for(int indexes = 0 ; indexes  < term.size(); indexes++){
                        		ResultSets = result.get(term.get(indexes));
                        		for(int inner = 0 ; inner < ResultSets.size() ; inner++){
                        			
                        			double add = ReturnResultSets.get(inner) + ResultSets.get(inner);
                        			
                        			ReturnResultSets.set(inner, add);
                        			add = 0.0;
                        		}
                        	}
                        
                        	ArrayList<Double> dummy = new ArrayList<Double>();
                        	dummy.addAll(ReturnResultSets);
                        	Collections.sort(dummy);
                        	Collections.reverse(dummy);
                        	for(int in1 = 0 ; in1 < dummy.size() ; in1++){
                        		

                        		for(int in2 = 0 ; in2 < ReturnResultSets.size() ; in2++){
                        			if(ReturnResultSets.get(in2) == dummy.get(in1)){
                        				System.out.println("( " + (in2 +1) + " , " + dummy.get(in1) + " )");
                        				ReturnResultSets.set(in2, -999999.0);
                        			}
                        		}
                        		

                        	}
                        }
                        else{
                        	 
                                System.out.println("must choose one");
                               
                        }
                        


        }
     /**
      * 
      * 
      * Helper function for hw4
      * */
        
        /***
         * Covert ArrayList to one string
         * 
         * */
        
        public static String ArrayListToString(ArrayList<String> bi){
        	
        	String binary = "";
        	for(int index = 0 ; index < bi.size() ; index++){
        		
        		binary += bi.get(index);
        	}
        	return binary;
        }
        
        /**
         * Function calculate the DFR value 
         * 
         * @param n: number of document
         * @param lt: it contains length of each document
         * @param ftd: it contains the ftd value for each term
         * @param terms: terms from query
         * @param lavg: average length of length
         * @param ld: length of each docuemt
         * 
         * @return result of dfr hashtable
         * **/
        
            public static Hashtable<String, ArrayList<Double>> getPone(int n ,
					Hashtable <String, Integer> lt ,
								Hashtable<String, ArrayList<Integer>> ftd , String terms, double lavg, ArrayList<Integer> ld){
				ArrayList<String> term = new ArrayList<String>();
				ArrayList<Integer> ftdvalue = new ArrayList<Integer>();
				ArrayList<Double> rightLog = new ArrayList<Double>();
				ArrayList<Double> leftLog = new ArrayList<Double>();
				Hashtable<String, ArrayList<Double>> returnValue = new Hashtable<String, ArrayList<Double>>();
				int ltvalue = 0;
				term = getTerms(terms);
				double logP1 = 0.0;
				double result = 0.0;
				double P2 = 0.0;
				double ftds = 0.0;
				
				
			
				for(int index = 0 ; index < term.size() ; index++){
				ltvalue = lt.get(term.get(index));
				
						for(int ii = 0 ; ii <  ftd.get(term.get(index)).size() ; ii++){
						ArrayList<Integer> ftdVal =  ftd.get(term.get(index));
						
							for(int iii = 0 ; iii < ftdVal.size() ; iii++){
							
							ftds = (double)ftdVal.get(iii) * (double)(Math.log(1.0 + ((double)lavg/(double)ld.get(iii)))/Math.log(2.0));
							
							
							logP1 =  (double)(Math.log(1.0+( (double)ltvalue/(double)n))/Math.log(2.0)) + (double)(ftds * (Math.log( 1.0 + ((double)n/(double)ltvalue))/Math.log(2.0)));
							
							rightLog.add(logP1);
							
							P2 = ftds/(ftds+1.0);
							
						
							result = ( 1.0- P2) * logP1;
						
							leftLog.add(result);
											
							}
						returnValue.put(term.get(index), leftLog);
						leftLog = new ArrayList<Double>();
						}
				
				}
				
				return returnValue;
				
				}
				
				public static Hashtable <String, Integer> queryCouter(String terms ){
				int counter = 0;
				Hashtable <String, Integer> counterTable = new Hashtable <String, Integer>();
				ArrayList<String> termArray = new ArrayList<String>();
				termArray = getTerms(terms);
				for(int index = 0 ; index < termArray.size() ; index++){
				counter = 0;
				for ( int j = 0; j < termArray.size(); j++ ){
				if (termArray.get(index).equals(termArray.get(j))){
				counter++;
				}
				counterTable.put(termArray.get(index), counter);
				}
			
				}
				
				return counterTable;
				}
        
        /**
         * It will create two file 
         * output: plan posting list: like...Delta {family=[213], clothes.=[107, 245],...
         * goutput: gamma posting list: like..GammaEncode {family=[00000001 1010101], clothes.=[0000001 101011, 00000001 0001010]
         * 
         * @param ArrayList<String>: keylist for Delta and Delta
         * @param Hashtable<String, ArrayList<Integer>> : Delta: collection of posting list
         * @param Hashtable<String, ArrayList<String>>  : GammaEncdoe: collection of posting list after convert Gamma value
         * @throws IOException 
         * 
         * */ 
        public static void writeGammaFileAndPlanFile(ArrayList<String> KeyList  , 
        								Hashtable<String, ArrayList<Integer>> Delta ,
        								Hashtable<String, ArrayList<String>> GammaEncode , String filename) throws IOException
        {
        	

        	String filecomtemp = "";
        	for ( int i = 0; i < filename.length(); i++){
    	    	if (filename.charAt(i) == '.'){
    	    		filecomtemp = filename.substring(0, i );
    	    	}
    	    }
        	
        	String filecom = filecomtemp + "_compress_bi";
        	String fileun = filecomtemp + "_compress_un";
        	FileWriter writer = new FileWriter(fileun +".txt");
        	FileWriter gwriter = new FileWriter(filecom+".txt"); 
        	String keyString = "";

        	keyString = " ";
        	/**
        	 * printing outpur.text
        	 * */
        	
        	for(int second = 0 ; second < KeyList.size() ; second++)
        	{
        		writer.write(KeyList.get(second) );

        			for(int four = 0 ; four < Delta.get(KeyList.get(second)).size() ; four++)
        			{
        				keyString += "  " + Delta.get(KeyList.get(second)).get(four);
        				
        			}
        			writer.write(keyString);
        			writer.write('\n');
        			keyString = " " ;

        	
        	}
        	
        	keyString = " " ;
        	/**
        	 * printing goutput.text
        	 * */
        	for(int second = 0 ; second < KeyList.size() ; second++)
        	{
        		gwriter.write(KeyList.get(second));

        			for(int four = 0 ; four < GammaEncode.get(KeyList.get(second)).size() ; four++)
        			{
        				keyString +=  " : " + GammaEncode.get(KeyList.get(second)).get(four);
        				
        			}
        			gwriter.write(keyString);
        			gwriter.write('\n');
        			keyString = " " ;

        	
        	}
        	
        	writer.close();
        	gwriter.close();
        }
        
        /**
         * Function is counting the number of term in one doc 
         * @param AllDocContainer: it contains all documents
         * @param String term: term query from the user input
         * 
         * 
         * @return ht: String: Term in the doc Integer part: doc counter 
         * 
         * 
         * */
        
        
        public static Hashtable <String, Integer> howmanytimeappearInDoc(HashMap<Integer, String>  AllDocContainer, String term){
        	ArrayList<String> al = new ArrayList<String>();
        	ArrayList<String> al2 = new ArrayList<String>();
        	int tracker = 0 ;
        	Hashtable<String, Integer> ht = new Hashtable<String, Integer>();
        	al = getTerms(term);
        
        	for(int index = 0 ; index < al.size() ; index++)
        	{
        		for(int inner = 1 ; inner <= AllDocContainer.size(); inner++){
        			
        			al2 = getTerms(AllDocContainer.get(inner));
        			for(int in = 0 ; in < al2.size() ; in++){
        				if(al.get(index).trim().equals(al2.get(in).trim())){
        					tracker++;
        					
        				}
        			}
        			
        		}
        		ht.put(al.get(index), tracker);
        		tracker = 0;
        		 al2 = new ArrayList<String>();
        	}
        	
        	return ht;
       	
        }
        /**
         * Transfer query into arraylist
         * @param the search terms in the query
         * @return arraylist that has the query term
         */
        public static ArrayList<String> getTerms(String terms)
        {
        	ArrayList<String> al = new ArrayList<String>();
        	
        	for(String t : terms.split(" "))
        	{
        		al.add(t);
        	}
        	
        	return al;
        	
        }
        
        
        /**
         * gammaEncoding is encoding gamma value
         * 
         * */
        public static ArrayList<String> gammaEncoding(ArrayList<String> al)
        {
        	ArrayList<String> reAl = new ArrayList<String>();
        	
        	for(int index = 0 ; index <al.size() ; index++)
        	{
        		if(al.get(index).equals("1"))
        		{	/** if ur us "1" then just "1" only exceptional case*/
        			reAl.add("1");
        		}
        		else
        		{	/**otherwise we call the "getGammaPreFix" to get 0001 style binary number
        			 *and we cut first diget from binary 
        			 * hen put these two strings together
        			 */
        			reAl.add(getGammaPreFix(al.get(index)) + " " +al.get(index).substring(1, (al.get(index).length())));
        			 
        			
        		}
        	}
        	return reAl;
        	
        }
        /**
         * get all the position for each term and store it into a hasttable.
         * @param AllDocContainer the hashMap that contain all of the document
         * @return the position of the document collection
         */
        public static Hashtable<String, ArrayList<Integer>> PositionIntheCollection(HashMap<Integer, String>  AllDocContainer ){
        	ArrayList<String> AlldocInDocList = new ArrayList<String>();
        	ArrayList<String> KeyList = new ArrayList<String>();
        	Hashtable<String, ArrayList<Integer>> DeltaBefore = new Hashtable<String, ArrayList<Integer>>();
        	Hashtable<String, ArrayList<Integer>> Delta = new Hashtable<String, ArrayList<Integer>>();
        	ArrayList<Integer> position = new ArrayList<Integer>();
        	                  	

        	AlldocInDocList = AlldocInOne(AllDocContainer);
        	KeyList = getKeys(AlldocInDocList);
        	Collections.sort(KeyList);
        	

        	
        	for(int first = 0 ; first < KeyList.size() ; first++)
        	{
        		for(int second = 0 ; second < AlldocInDocList.size() ; second++)
        		{
        			if(KeyList.get(first).equals(AlldocInDocList.get(second))){
        				 

        				position.add(second + 1);
        				

        			}
        		}
        		DeltaBefore.put(KeyList.get(first), position);
        		 position = new ArrayList<Integer>();
        	}
        	position = new ArrayList<Integer>();
        	

        	
        	return DeltaBefore;
        	

        }
        /**
         * Get all unique keys from the AllDocContainer
         * 
         * it will be keys to use  for PositionIntheCollection
         * 
         * how to use ? : getKeySet(AllDocContainer);
         * 
         * @param AllDocContainer : collection of all doc
         * @return KeyList : key list
         * */
        public static ArrayList<String> getKeySet(HashMap<Integer, String>  AllDocContainer){
        	ArrayList<String> KeyList = new ArrayList<String>();
        	ArrayList<String> AlldocInDocList = new ArrayList<String>();
        	AlldocInDocList = AlldocInOne(AllDocContainer);
        	KeyList = getKeys(AlldocInDocList);
        	Collections.sort(KeyList);

        	return KeyList;
        }
        /**
         * 
         * @param AllDocContainer contain all of the doucments in a hashMap
         * @param term the string of the query 
         * @return 
         */
        public static Hashtable <String, ArrayList<Integer>> getftd(HashMap<Integer, String>  AllDocContainer   , String term){
        	ArrayList<String> al = new ArrayList<String>();
        	ArrayList<String> al2 = new ArrayList<String>();
        	ArrayList<Integer> track = new ArrayList<Integer>();
        	int tracker = 0 ;
        	Hashtable<String, ArrayList<Integer>> ht = new Hashtable<String, ArrayList<Integer>>();
        	al = getTerms(term);
        
        	for(int index = 0 ; index < al.size() ; index++)
        	{
        		for(int inner = 1 ; inner <= AllDocContainer.size(); inner++){
        			
        			al2 = getTerms(AllDocContainer.get(inner));
        			for(int in = 0 ; in < al2.size() ; in++){
        				if(al.get(index).trim().equals(al2.get(in).trim())){
        					tracker++;
        					
        				}
        			}
        			track.add(tracker);
        			tracker = 0;
        		}
        		ht.put(al.get(index), track);
        		track = new ArrayList<Integer>();
        		 al2 = new ArrayList<String>();
        	}
        	
        	return ht;
       	
        }
        /**
         * get the prefix of the binary string
         * @param BinaryNum: the binary string of that binary number
         * @return the gama code for that binary number
         */
        
        public static String getGammaPreFix(String BinaryNum)
        {
        	int digit = BinaryNum.length();
        	String reVal = "01";
        	String one = "";
        	for(int index =2; index < digit ; index++)
        	{
        		one +="0";
        	}
        	return one+reVal;
        	
        	
        }
        
        /**
         * Convert Dec value to Binary
         * @param ArrayList<Integer>: decimal number
         * @return ArrayList<String>: String type binary number
         * */
        
        public static ArrayList<String> DecToBinary(ArrayList<Integer> al)
        {
        	ArrayList<String> reAl = new ArrayList<String>();
        	for(int index = 0 ; index < al.size() ; index++)
        	{
        		reAl.add(Integer.toBinaryString(al.get(index)));
        	}
        	
        	return reAl;
        }
        
        
        /**
         * find gap between number and number
         * @return ArrayList<Integer> delta value
         * */
        
        public static ArrayList<Integer> FindGap(ArrayList<Integer> al){
        	ArrayList<Integer> reVal = new ArrayList<Integer>();
        	int temp = 0;

        	if(al.size() == 1){
        		reVal.add(al.get(0));
        		
        	}
        	else
        	{
        		reVal.add(al.get(0));
        		for(int index = 1 ; index < al.size() ; index++)
        		{
        			int front = al.get(index);
        			int end = al.get(index-1);
        			temp = front - end;
        			reVal.add(temp);
        			temp = 0;
        		}
        	}
       
        	return reVal;
        	
        	
        }
        
        
        /**
         *  GetKeys: get the unique key from the all doc.
         *  @param al ArrayList<String> : AllDocContainer: contain all doc wih doc number.
         *  @return reVal ArrayList<String> : unique key
         * */
         public static ArrayList<String> getKeys(ArrayList<String> al)
         {
         	ArrayList<String> reVal = new ArrayList<String>();
         	for(int index = 0 ; index < al.size() ; index++){
         		
         		if(!reVal.contains(al.get(index))){
         			reVal.add(al.get(index));
         		}
         		
         	}
         	return reVal;
         	
         	
         }
       /**
        * AlldocInOne
        * AllDocContainer: has all term however it is seperate by doc number
        * In order to do gamma code, we need put all doc in the one array list (because we need position.)
        * 
        * @param AllDocContainer: contain all doc wih doc number.
        * @return al<string> this list contain all document in the one arraylist.
        * Index= position of document 
        * 
        * 
        * */
       public static ArrayList<String> AlldocInOne(HashMap<Integer, String>  AllDocContainer)
       {
     	  ArrayList<String> al  = new ArrayList<String>();
     	  ArrayList<String> hashtoValue = new ArrayList<String>(AllDocContainer.values());
     	  for(int index = 0 ; index  < hashtoValue.size() ; index++)
     	  {
     		  String str =  hashtoValue.get(index);
     		  
     		  StringTokenizer st = new StringTokenizer(str);
     		  while(st.hasMoreElements()){
     			  
     			 al.add((String) st.nextElement());
     		  }
     		  
     	  }
     	 
     	  return al;
       }
        
     /**
      * 
      * HW4 Function end
      * 
      * */
        

        
	/**
	 * Helper Function  for hw3
	 * 
	 * 
	 */
       /**
        * 
        * BM25IDF: function is getting all IDF value for all word in query 
        * 
        * @param Hashtable<String , Integer> : it contain information for demominator for IDF
        * @param int totalnumberofdoc : it is total number of document 
        * @param String[] bm25QueryList contains all query
        * 
        * @return Hashtable<String, Double>  reht: Key: word in query  Value: IDF value 
        * 
        * */
        
      public static Hashtable<String, Double> BM25IDF( Hashtable<String , Integer> ht , int totalnumberofdoc, String[] bm25QueryList)
      {
    	  Hashtable<String, Double>  reht = new Hashtable<String, Double>();
    	  double reVal = 0.0;
    	  for(int first = 0 ; first < bm25QueryList.length ; first++)
    	  {
    		  reVal += Math.log(((double)totalnumberofdoc/(double)ht.get(bm25QueryList[first])))/Math.log(2.0);
    		  reht.put(bm25QueryList[first], reVal);
    		  
    		  reVal = 0.0;
    	  }

    	 return reht;
      } 
      
      
      /**
       * Get BM25 for TF
       * First, get the all term from the each document. So, we use allDocInArrayList and term to count how many "bob"
       * 		is in the each document.
       * Second, go to second for loop to can calculate the TF value for one term and each document 
       * 		like "bob" for each doc 
       * 		if there is "hi bob" then calculate "hi" first then "bob" next.
       * for default: k1 and b are usually set of 1.2 and 0.75 
       * bm25Container is for store each bm25 value
       * @param avgLength : average length of doc
       * @param allDocInArrayList : arraylist which contain all doc in string type
       * @param howManytimeAppearInDoc : how may time term appear on each doc
       * @param bm25QueryList: query term  like "hello bob"
       * @param lengthOfAllDoc: Integer type arraylist which contain length of each doc
       * 
       * @return ArrayList<Double> it contains TF value for one term.
       *  
       * */
      public static ArrayList<Double>  BM25TF(double avgLength , ArrayList<String> allDocInArrayList  , String bm25QueryList , ArrayList<Integer> lengthOfAllDoc)
      {
    	  
    	  double k  = 1.2;
    	  double b = 0.75;
    	  double numerator = 0.0;
    	  double denominator = 0.0;
    	  double finalBM25 = 0.0;
    	  int tracker = 0 ;
    	  ArrayList<Integer> countTermInEachDoc = new ArrayList<Integer>();
    	  ArrayList<Double> bm25Container = new ArrayList<Double>(); 
    	  /**
    	   *  getting how many word in term appear in each doc  	  
    	   */
      	 for(int outer = 0 ; outer < allDocInArrayList.size() ; outer++)
      	 {
      		String sentance =  allDocInArrayList.get(outer);  
      		for(String Str :sentance.split(" ") )
      		{
      			/**if word in sentence is equal to term.
      			 * increase tracker
      			 */	
      			if(Str.equals(bm25QueryList))
      			{
      				tracker++;
      			}
      		
      		}
      		/**
      		 * store in the counter of term in the countTermInEachDoc
      		 */
      		countTermInEachDoc.add(tracker);
      		tracker = 0 ; 
      	 }
      	 /**
      	  *  calculate actual BM25TF
      	  */
    	 for(int first = 0 ; first <countTermInEachDoc.size() ; first++ )
    	 {
    		 numerator = (double)((countTermInEachDoc.get(first) * (k+1)));
    		 denominator = (double)((countTermInEachDoc.get(first)) + k*((1-b) + b*((double)lengthOfAllDoc.get(first)/avgLength)));
    		 finalBM25 = (numerator/denominator);
    		 bm25Container.add(finalBM25);
    		 numerator = 0.0;
    		 denominator = 0.0;
    		 finalBM25 = 0.0;
    	 }

    	 return bm25Container;
    	  
    	  

    	  
      }
      /**
       * Get total length of all doc
       * 
       * @param Arraylist which contains length of all doc
       * @return total length of all docuement 
       * */
      public static int totalLength(ArrayList<Integer> lengthOfAllDoc)
      {

      	 int tracker = 0 ;
      	 
      	 
      	 for(int outer = 0 ; outer < lengthOfAllDoc.size() ; outer++)
      	 {

      		tracker += lengthOfAllDoc.get(outer);
      		      		 
      	 }
      	 return tracker;
      }
        
     /**
      * 
      * counting term in the all document
      * 
      * @param terms: each query 
      * @param doc : containing all documents
      * 
      * @return al: arraylist index = doc number , value = how many time term appear
      * 
      * */
     public static ArrayList<Integer> CountingNumberOfTermInDoc(String terms, ArrayList<String> doc)
     {
    	int tracker = 0 ;
    	ArrayList<Integer> al = new ArrayList<Integer>();
    	for(int outer = 0 ; outer < doc.size(); outer++){
    		String sentance =  doc.get(outer);   	
		    	for(String Str: sentance.split(" "))
				{
						if(terms.equals(Str))
						{
							tracker++;
						}
				}
		    	al.add(tracker);
		    	tracker = 0;
    	}
  
    	return al;
     
     }
        
       /**
        * howManyTimeAppear : counting how many times terms appear in the all doc
        * How ? : 1. get string type sentance from the each doc 
        * 		  2. then useing trim and split to get each word in doc
        * 		  3. if word in term and word in doc is equal then increase counter
        * @param al : arraylist for all doc. 
        * @param terms: quries 
        * */
        
        public static Hashtable<String , Integer> howManyTimeAppear(ArrayList<String> al , String[] terms)
        {
        	int outer;
        	int inner;
        	int counter = 0;
        	
        	Hashtable<String, Integer> ht = new Hashtable<String, Integer>();
        	for(outer = 0 ;outer  < terms.length ; outer++)
        	{
        		for(inner = 0; inner < al.size() ; inner++)
        		{
        			String sentance = al.get(inner).toString();
        			for(String Str: sentance.split(" "))
        			{
        				if(terms[outer].trim().equals(Str.trim()))
        				{
        					counter++;
        					
        					break;
        				}
        				
        			}
        			
        		}
        		ht.put(terms[outer], counter);
        		counter = 0;
        	}
        	
        	return ht;
        }
        
      /**
       * this function caluclate the avg of length 
       * of all docmument
       * how ? (total length of doc) / (number of doc)
       * @param length of each doc
       * @return average length of all doc
       * */
        public static double avg(ArrayList<Integer> al)
        {
        	double totalNum = 0.0;
        	double avg = 0;
        	int index ;
        	for(index = 0 ; index < al.size() ; index++)
        	{
        		totalNum+=al.get(index);
        	}
        	avg = (double)(totalNum / (double)al.size());
        	
        	return avg;
        }
        
        static void indexingHash(HashMap<Integer, String>  AllDocContainer, int docNum)
        {
        	ArrayList<String> temp = new ArrayList<String>();
        	ArrayList<Integer> pos  = new ArrayList<Integer>();
        	int noTermsDoc=0;
        	String text = AllDocContainer.get(docNum);
        	for(String t : text.split(" "))
        	{	
        		temp.add(t);
        	}
        	
        	noTermsDoc = temp.size();
        	for(int j=0; j<noTermsDoc; j++)
        	{
        		collTermPos++;
        		if(termPosList.containsKey(temp.get(j).trim()))
        		{
        			termPosList.get(temp.get(j)).add(collTermPos);
        		}
        		else
        		{
        			pos.add(collTermPos);
        			termPosList.put(temp.get(j),pos);
        			pos  = new ArrayList<Integer>();
        		}
        		
        	}
        }
        
        static void merge() throws IOException, InterruptedException
        {
        	int gen=0;
        	
        	ArrayList<String> keysets = new ArrayList<String>();
          
        	
        	
        	gen++;
        	File g = new File(Integer.toString(gen)+".txt");
        	
        	String readingLine = "";
        	BufferedReader br  = null;
        	
        	while(g.exists())
        	{
        		
        		ArrayList<Integer> temp = new ArrayList<Integer>();
        		br = new BufferedReader(new FileReader(g));
        		while((readingLine = br.readLine()) != null)
        		{
        			
        		        		
        			
        			String[] keyword = readingLine.split(" ");
        			String term = keyword[0];
        			
        			for( int k=1; k < keyword.length;  k++)
        			{
        				temp.add(Integer.parseInt(keyword[k]));
        			}	
        		
        			if(termPosList.containsKey(term))
        			{
        				termPosList.get(term).addAll(0,temp);
        			}
        			else
        			{
        				termPosList.put(term, temp);
        			}
        			temp = new ArrayList<Integer>();
        		}
        			br.close();
        			g.delete();
        			gen++; 
        			g = new File(Integer.toString(gen)+".txt");
        			
        	}
        	
        	Enumeration e = termPosList.keys();
        	while(e.hasMoreElements())
        	{
        		keysets.add(e.nextElement().toString());
        	}   	
        	Writer out = null;

        	
        	FileWriter writer =  new FileWriter(Integer.toString(gen)+".txt");
        	String line = "";
        	

        		for(int i = 0 ; i < keysets.size() ; i++)
        		{
        			ArrayList<Integer>  all = termPosList.get(keysets.get(i));
        			line += (keysets.get(i) + " ");
        			for(int ii = 0 ; ii < all.size() ; ii++)
        			{
        				line += (Integer.toString(all.get(ii)) + " ");
        			}
        			writer.write(line + System.getProperty( "line.separator" ));
        			
        			line = "";
        			
        		}	
        	
        	writer.close();
        	Thread.sleep(5000);
			termPosList = new Hashtable<String, ArrayList<Integer>>();
        }
        
        
        
        
        
        static void logrithmicMerge(HashMap<Integer, String>  AllDocContainer) throws IOException, InterruptedException
        {
        	Hashtable<String,ArrayList<Integer>> termPosList = new Hashtable<String,ArrayList<Integer>>();
        	int numDoc = AllDocContainer.size();
        	int i=0;
        	
        	for(i=1; i<= numDoc; i++)
        	{
        		indexingHash(AllDocContainer,i);
        		if(i%5 == 0)
        		{
        			merge();
        		}
        	}
        	if( ((i-1) %5) != 0)
        	{
        		merge();
        	}
        }
        
        
      /**
       * DetermineLenth: it is determining all doc's lengths for BM25
       * 
       * Using for loop counting the words to get the length of each doc
       * 
       * @param ArrayList<String> it might contain all docuement   
       * @return ArrayList<Integer>: length of each doc (how many words are in each doc)
       */
        
      public static ArrayList<Integer> DetermineLenth(ArrayList<String> al)
      {
     	 ArrayList<Integer> reAl = new ArrayList<Integer>();
     	 int tracker = 0 ;
     	 String something = ""; 
     	 
     	 for(int outer = 0 ; outer < al.size() ; outer++)
     	 {
     		String sentance =  al.get(outer);  
     		for(String Str :sentance.split(" ") )
     		{
     			something = Str;
     			tracker++;
     		
     		}
     		reAl.add(tracker);
     		tracker = 0;
     		 
     	 }
     	 
     	 return reAl;
     	 
      }     
        
        
        
     /**
      * HashvalueToArrayList: Convert hash table's value to the ArrayList
      * @param hashtable<Integer, String>
      * @return ArrayList<String>
      * 
      * This is using for loop to put hash value(String type) to arraylist
      * */
      public static ArrayList<String> HashvalueToArrayList(HashMap<Integer, String> allDocContainer)
      {
    	  ArrayList<String> al = new ArrayList<String>();
    	  int index;
    	  for(index = 1 ; index < allDocContainer.size() + 1; index++)
    	  {
    		  al.add(allDocContainer.get(index));
    	  }
    	  return al;   	  
      }
        
       /**
        * prepare to calculate Proximity Score
        * @param term it is a string array that has all the query term
        * @param hm it is a hashmap that store the document id with String of document 
        * @param docNo it is an int that has the document number
        */
      static void findTermIndex(String[] term, HashMap<Integer, String> hm,int docNo)    
      {
              int index=0,startIndex=0,wordIndex=0;
      		String text = new String();
      		  
      		ArrayList<Integer> indexList = new ArrayList<Integer>();
              
              text = hm.get(docNo);
              String[] doc = text.split(" ");
              
              for(index=0;index<term.length;index++)
              {	
              	for(int i=0;i<doc.length;i++)
              	{
              		if(term[index].equals(doc[i]))
              		{
              			indexList.add(i+1);
              		}
              	}
              	               	
              	termIndexList.put(term[index],indexList);
              	indexList = new ArrayList<Integer>(); 
                   
             }	
             calcProximityScore(termIndexList, docNo, term);
             
      } 
      
      /**
       * calculating proximity ranking
       * @param ls is an hashtable with term index list
       * @param docNo it is an int that has the document number
       * @param term it is a string array that has all the term
       */
      static void calcProximityScore(Hashtable<String,ArrayList<Integer>> ls,int docNo,String[] term)
      {
      	int i=0,j=0,u=10000,v=0,position=0,temp=0;
      	double proximityScore=0.0;
      	       	       	
      	while( position >= 0 )
      	{
      		u=10000;
      		for (i=0; i< term.length; i++)
      		{
      			temp=next(ls,position,term[i]);
      			if(v < temp && temp != 10000)
      			{
      				v=temp;
      			}
      			if( temp == 10000 )
      			{	
      				v=temp;
      				position = -1;
      				break;
      			}	
      		}
      		if(v!=10000) 
      		{
      			for (i=0; i< term.length; i++)
          		{
          			temp=prev(ls,v+1,term[i]);
          			if(u > temp && temp != -1)
          			{
          				u=temp;
          				position=temp;
          			}
          			if(temp == -1 || u==10000)
          			{
          				position = temp; 
          				break;
          			}
          		}	
      			
      		}
      		if( position != -1)
      		{	
      			proximityScore = proximityScore + ((double)(1.0)/ (((double)v-(double)u) + 1.0));
    			System.out.println("(" + docNo + "," + proximityScore+ ")");
    			        			
    			hashDocProxScore.put(docNo,proximityScore);
      		}

      	}	
      
      }
      
      /***
       * hw3 next with possiton
       * @param ls is a hashtable that has all the term with times it appear
       * @param position is the current position
       * @param term is a string of input query term
       * @return the next position
       */
      static int next(Hashtable<String,ArrayList<Integer>> ls,int position,String term)
      {
      	int index=0,v=0;
      	
      	while(index < ls.get(term).size() && ls.get(term).get(index) <= position)
      	{
      		index++;
      	}
      	if( index >= ls.get(term).size() )
      	{
      		v=10000;
      	}
      	else
      		v=ls.get(term).get(index);
      	return v;
      }
      
      /***
       * hw3 prev with position
       * @param ls is a hashtable that has all the term with times it appear
       * @param position is the current position
       * @param term is a string of input query term
       * @return the prev position
       */
      static int prev(Hashtable<String,ArrayList<Integer>> ls,int position,String term)
      {
      	int index=0,u=0;
      	
      	index= ls.get(term).size()-1;
      	
      	while(index >= 0 && ls.get(term).get(index) >= position)
      	{
      		index--;
      	}
      	if( index < 0 )
      		u=-1;
      	else
      		u=ls.get(term).get(index);
      	
      	return u;
       }
      
      
      static double DFRCal (int lt, int N, int ftd){     
	      double logP1 = 0.0;
	      double P2 = 0.0;
	      double result = 0.0;
	   
	      logP1 = Math.log(1+ lt/N) + ftd * Math.log( 1 + N/lt);
	      P2 = ftd /( ftd +1);
	     
	      result = (1-P2)*( -logP1) ;
	      return result;
      }
      
      /**
       * 
       * End of helper function for hw3
       * */
      
        
   /**
    * Helper function for hw2
    * 
    * */     
    
	/** 
	 *	For Printing New Line
	 */
        public static void NewLine()
        {System.out.println();}
	/** 
	 * For reversing the ArrayList
	 */
        public static void ReverceList(ArrayList<Integer> al)
                {Collections.reverse(al);}
       /**
        *Clearing contents inside of Hashtable
        *
        public static void free(Hashtable ht)
                {ht.clear();}*/
       /**
     	* @param word: it is the querry term
     	* @return return the number of words in the querry
     	* Counting how many works in the String.
     	*/
        public static int CountingWord(String word)
        {
                 String[] arr = word.split(" ");
                 int length = arr.length;               
                 return length;
                
        }
        /**
         * @param1 term the signle word of the term from querry
         * @param2 docNum document number
         * @param3 hm hashmap that has all to document
         * @return true or false to check word is inside the document or not
         */
        public static boolean checkWordIsInsideOrNot
                        (String term , int docNum ,  HashMap<Integer, String> hm )
        {
                String text = hm.get(docNum);
                String patternString = " " + term+" " ;
                String patternString1 = term+" ";
                Pattern pattern = Pattern.compile(patternString);
                Pattern pattern1 = Pattern.compile(patternString1);
                Matcher matcher = pattern.matcher(text);
                Matcher matcher1 = pattern1.matcher(text);
                if (matcher1.find() || matcher.find()){
                	return true;
                }else{
                	return false;
                }
               
        }
        
	/**
	 * @param1 word: This is the term to past in for spliting to words
	 * @return arr:  return to a String array that has splitted words. 
	 * spliting each words from the String 
	 * and sort into array and return the word containers
	 */
        public static String[] returnWord(String word)
        {
                 String[] arr = word.split(" ");                   
                 return arr;    
        } 
        /** Function: Returning  numnber of term in the each document
         * 
         * @param1 TermArray: This array contain words in query like [1] = "Hello" [2] ="new"
         * @param2 docHashMap: contain each docs  like docHashMap = docHashMap
         * @return case1: if doc contains all words will return {hello=2, new=1}
         * @return case2:query [1] = "Hello" [2] ="new" [3] = "cool"
         * then doc is missing "cool", so it will return -9999999 
         * First, get each how many times words is in the doc 
         * Second once we get the all value and all term is appear
         * then go to else case and using iterator to get int value from the keyword "term"
         * Third, we call CalTF and CalIDF to get each value
         * fourth , we cal tf-idf value and return it
         */
        public static float getTFIDF
          (String [] TermArray , HashMap <Integer, String> docHashMap, int docnumber , int totalnumberofdocs , int whatsize)
        {
                int reVal = 0;
               
                String doc = docHashMap.get(docnumber).toString();
               
                int index ;
                String keyword = " ";
              
                Map<String,Integer> hmap= new HashMap<String,Integer>();
                for(index = 0 ; index < TermArray.length ; index++)
                {
                        for(String Str : doc.split(" "))
                        {
                                keyword = Str;
                            
                                if(TermArray[index].equals(Str))
                                {
                                        reVal++;        
                                        hmap.put(keyword, reVal);
                                }
                                
                        }
                        reVal = 0;
                }
                
                if((hmap.size() != TermArray.length))
                {
                        return -9999999;
                }
                else
                {
                
                        Set set = hmap.entrySet();
                        Iterator it = set.iterator();
                        int valuefortf = 0;
                        double tf = 0.0;
                        double idf = 0.0;
                        float tfidf;
                        float finalValue = 0;
                        while(it.hasNext())
                        {
                                Map.Entry m = (Map.Entry)it.next();
                                valuefortf = (Integer)m.getValue();
                                tf = CalTF(valuefortf);
                                idf=CalIDF(totalnumberofdocs, whatsize);
                                tfidf = (float)tf * (float)idf;
                                finalValue = tfidf;
                        }

                        return finalValue;
                }
                
        }
        
    
    /**
     * @param howmaytimetermInKeyWord: how many time the term appear in one document
     * @return tf value
     * cal TF value for each term
     * */
    static double CalTF(int howmaytimetermInKeyWord)
    {
                                            
            double  tf = 
            (Math.log(howmaytimetermInKeyWord)/Math.log(2) )+ 1;
            
            return tf;
    }
        
    /**
     * @param1 totalnumberOfDocs = the total numbers of document
     * @param2 howmaytimetermInKeyWord: how many time the term appear in the file
     * @return value of idf
     * cal IDF
     */
    static double CalIDF(int totalnumberOfDocs , int howmaytimetermInKeyWord)
    {
            double idf = 
            Math.log((double)((double)totalnumberOfDocs/(double)howmaytimetermInKeyWord))/Math.log(2);

            return idf;
            
    }

    /**
     * @param1 term = the term in the given query
     * @param2 hm: a hashmap that store the index and the query words
     * @param3 totalDocs: how many time the term appear in the file
     * helper function for next and prev to date document list
     */
        
        static void updateDocList(String term, HashMap<Integer,String> hm, int totalDocs)
        {
                String text = new String();
                int i=0,temp=0;
                temp = totalDocs;
        
                for(i=1;i<=temp;i++)
                {       
                        text = hm.get(i);
                        String patternTerm = " "+term +" ";
                        
                        Pattern pattern = Pattern.compile(patternTerm);
                        
                        Matcher matcher = pattern.matcher(text);
                        
                        if(matcher.find() || matcher.find())
                        {
                                
                        	docNumber1.get(docCount).add(i);
                                
                                
                        }
                }
                termDocList.put(term,docNumber1.get(docCount));
                
                docCount++;
                }

        /**
         * @param1 term: the term from querry
         * @param2 docNo: document number
         * @param3 hm hashmap that has all to document
         * @return 0 or 1 for finding the term in the document or not.
         */    
        static int searchTerm (String term, int docNo , HashMap<Integer, String> hm)    
        {
                String text = new String();
                
                text = hm.get(docNo);
                docScore[docNo-1]= ((double)1/((double)docNo +(double)1));
                
             
                String patternTerm = " "+term +" ";
                String patternString1 = term+ " ";
                Pattern pattern = Pattern.compile(patternTerm);
                
                Pattern pattern1 = Pattern.compile(patternString1);
                Matcher matcher = pattern.matcher(text);
                Matcher matcher1 = pattern1.matcher(text);
                
                
                if(matcher.find() || matcher1.find())
                        return 1;
                else
                        return 0;
        }

       /**
        * helper function for eval boolean expresstion
        */        
        static int eval()
        {
                int op1=0,op2=0,size=0;
                String token;
                size = tokenList.size();
                Stack<Integer> stack = new Stack<Integer>();
                
                
                for(int i=size-1;i>=0;i--)
        {
            token = tokenList.get(i);
            while( !token.equals("*") && !token.equals("+") && !token.equals("-"))
            {
                stack.push((Integer) hashTermSearch.get(token));   
                i--;
                if(i>-1)
                {       token = tokenList.get(i);}
                else
                        {break;}
            }
                if(token.equals("*") || token.equals("+") || token.equals("-") )
            {
                if(token.equals("*"))
                {
                        op1=stack.pop();
                        op2=stack.pop();
                        if(op1 ==1 && op2==1)
                                op1=1;
                        else
                                op1=0;
                        stack.push(op1);
                }
                if(token.equals("+"))
                {
                        op1=stack.pop();
                        op2=stack.pop();
                        if( op1==1 || op2==1)
                        {op1=1;}
                        else
                        {op1=0;}        
                        stack.push(op1);
                }
                if(token.equals("-"))
                {
                        op1=stack.pop();
                        if(op1==1)
                        { op1=0;}
                        else if(op1 == 0)
                        {op1=1;}
                        stack.push(op1);
                }       
             }
         }
                return (stack.pop());
        }            
        
     	 /**
      	  * @param1 s the signle word of the term from querry
	  * @param2 numofdoc document number
	  * @param3 hm hashmap that has all to document
	  * @return 0 or 1 to caluclate boolean expresstion 
      	  */
        
        public static int calculate(String s , int numofdoc , HashMap<Integer, String> hm)
        {
                int n,i=0,flag=0,j=0,k=0,totTerms=0,containsOpr=0;
                char ch;
                String word;
                int index=0;

                docScore=new double[numofdoc];
                docFlag=new int[numofdoc];
                StringBuilder builder = new StringBuilder();
                
                
                n=s.length();
                
                while(index<n)
                {
                        ch=s.charAt(index);
                        if((ch == '*') || (ch == '+') || (ch == '-'))
                        {
                                containsOpr=1;
                                break;
                        }
                        index++;
                }
                
                for(i=0;i<n;i++)
                {
                        ch= s.charAt(i);
                        
                        while(ch != '+'  && ch!='-' && ch!='*' && ch!=' ')
                        {                               
                                flag=1;
                                builder.append(ch);
                                i++;
                                if(i<n)
                                {
                                        ch= s.charAt(i);
                                }
                                else
                                break;  
                        }
                        if(flag == 1)
                        {
                                flag=0;
                                totTokens++;
                                totTerms++; /*Number of words in the query*/
                                word = builder.toString();
                                tokenList.add(word);
                                termArr[k]=word;
                                k++;
                                builder.delete(0,builder.length());
                                word= " ";
                        }
                        
                        if((ch == '*') || (ch == '+') || (ch == '-'))
                        {       
                                totTokens++;   /**tokens in the query*/
                                tokenList.add(Character.toString(ch));
                        }       
                        
                }
                
                if(containsOpr == 0)
                {
                        String temp;
                        int size = tokenList.size(),m=0;
                        
                        if(size > 1)
                        {       
                                for(m=size-1;m<=0;m--)
                                {
                                        temp = tokenList.get(m);
                                        tokenList.add((size+m),temp);
                                }
                                m=0;
                                temp = "*";
                                for(m=0;m<size-1;m++)
                                {
                                        tokenList.add(m,temp);
                                }
                        }                       
                }
                
                for(i=0;i<numofdoc;i++)
                {
                        for(j=0;j<totTerms;j++)
                        {/**
                         * here i+1 is the doc number
                        */
                                hashTermSearch.put(termArr[j],searchTerm(termArr[j],i+1, hm)); 
                        }
                        docFlag[i]=eval();
                }
        
                return 0;
        }
        
        /**
         *  @param1 key: the term to serach in whole file
         *  serarch whole document to find the term  
         *  where it first appear
         *  @return the fist document id where the term appear 
         */      

    public static int first(String key)
    {
        int first = 0;
        
        ArrayList<Integer> temp = termDocList.get(key);
      
        if ( temp.get(0) != 0){
                first = temp.get(0);
                return first;
        }else
                return 0;

 
    }

        /**
         *  @param1 key: the term to serach in whole file
         *  serarch whole document to find the term  
         *  where it last appear
         *  @return the last document id where the term appear 
         */   
        public static int last(String key)
        {
        
        int last = 0;
        
        ArrayList<Integer> temp = termDocList.get(key);
        
        int size=temp.size();
       
        if (size != 0){
                
                last = temp.get(size-1);
                return last;
        }
        else
                return 0;
        }

	/**
	 * @param1 s: it is the term from the query
	 * @param2 low: starting position
	 * @param3 hight: end position
	 * @param4 current: current position
	 * @param5 temp: arraylist of integer that has docid 
	 * @return the position of the document 
	 */
        public static int binarysearch(String s, int low, int high, int current,ArrayList<Integer> temp)
        {
                double mid=0;
                                
                while((high-low) >1)
                {
                        mid = Math.floor((double)(low + high)/(double)2);
                        
                        if( temp.get((int)mid) <= current)
                                low = (int)mid;
                        else
                                high = (int)mid;
                }
                
        return high;
        }

	/**
	 * @param1 s: it is the term from the query
	 * @param2 low: starting position
	 * @param3 hight: end position
	 * @param4 current: current position
	 * @param5 temp: arraylist of integer that has docid 
	 * @return the position of the document 
	 */
        
        public static int binarysearchprev(String s, int low, int high, int current,ArrayList<Integer> temp)
        {
                double mid=0;
                                
                while((high-low) >1)
                {
                        mid = Math.floor((double)(low + high)/(double)2);
                        
                        if( temp.get((int)mid) < current)
                                low = (int)mid;
                        else
                                high = (int)mid;
                }
                
        return low;
        }
        
        /**
         * @param1 the term to serach in document
         * @param2 the given document id to start 
         *  serarch prev document that has the term
	 * @return prev document id
         *  where preview appear in given document id
         */
        public static int prev(String key, int current)
        {
        
		int temp = first(key);
		int next_id = next(key, temp);
		int last_term = last(key);

		
		int result = 0;
		if (next_id >= current){
			return temp;
		}
		else if (current > last_term){
			current = last_term;
			return current;
		}
		else{
		 for ( int i = next_id; i < current; i++){
			if ( next(key,i) >= current)
				result = next(key, i-1);
				

		}

		}
		return result;
    }
 
        /**
         * @param1 the term to serach in document
         * @param2 the given document id to start 
         *  serarch next document that has the term
	 * @return next document id
         *  where next appear in given document id
         */

        public static int next(String term, int current)
        {
                ArrayList<Integer> temp = termDocList.get(term);
                
                
                int lt=0,low=0,high=0,jump=0;
                lt=temp.size();
                
                if((lt == 0) || (temp.get(lt-1) < current))
                {return 0;}
                if(temp.get(0) > current)
                {
                        cache = 0;
                        return temp.get(cache);
                }
                if((cache>0) && (temp.get(cache-1) <= current))
                        low=cache-1;
                else
                        low=0;
                
                jump=1;
                high=low+jump;
                
                while ((high < lt) && (temp.get(high) <= current))
                {
                        low = high;
                        jump=(2*jump);
                        high = low + jump;
                }
                if(high > lt)
                {
                        high = lt;
                }
                cache = binarysearch(term,low,high,current,temp);
                
                return temp.get(cache);
        }
        

        
        static int CountDocs(String term){
                int x = 0;
                int count = 0;
                x = next(term, 0);
                
	                while (x != 0){
		                count++;
		                cache = tc;
		                x = next(term,x);
	               }
                return count;
       }
}               